#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using ll = int64_t;

const int MAXN = 500 + 5;
const int MAXK = 100 + 5;

int n;
int k;

struct P {
    ll x, y;
    bool operator<(const P &other) const {
        if (x != other.x)
            return x < other.x;
        return y < other.y;
    }
} p[MAXN];

int dp[MAXN][MAXK];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        std::cin >> p[i].x >> p[i].y;
    }

    std::sort(p + 1, p + n + 1);

    ll maxlen = 0;

    for (int i = 1; i <= n; i++) {

        dp[i][0] = 1;

        for (int j = 1; j < i; j++) {

            if (p[j].y <= p[i].y) {

                ll dist = (p[i].x - p[j].x) + (p[i].y - p[j].y);

                if (dist <= 0)
                    continue;

                ll cost = dist - 1;

                for (int pk = 0; pk <= k; pk++) {

                    if (dp[j][pk] > 0) {
                        ll tot = pk + cost;
                        if (tot <= k) {

                            int nlen = dp[j][pk] + dist;

                            dp[i][tot] = std::max(dp[i][tot], nlen);
                        }
                    }
                }
            }
        }
    }

    maxlen = k + 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (dp[i][j] > 0) {

                maxlen = std::max(maxlen, (ll)dp[i][j] + (k - j));
            }
        }
    }

    std::cout << maxlen << "\n";

    return 0;
}
